The previous slide introduced the restricted stack operations (Push, Pop, Peek) governed by the `top` index. This strict access restriction is the critical enforcer of the stack's defining rule: the FILO (First In, Last Out) principle.
- The FILO principle dictates the temporal relationship between insertion and removal: the last element pushed onto the stack will always be the first element popped off.
- This structure is essential for applications requiring reversal of order or tracking execution history (like function call stacks).
- Definition: FILO implies that an element cannot be accessed or removed unless all elements placed on top of it have already been removed. The pointer `top` always targets the most recent element.
Stack Operations & Complexity
| Operation | Description | Complexity |
|---|---|---|
| Push | Add an element to the top. | $O(1)$* |
| Pop | Remove element from the top. | $O(1)$ |
| Peek / Top | View the top element. | $O(1)$ |
| Search | Find an element in the stack. | $O(n)$ |
* $O(1)$ amortized for dynamic arrays.